Search results for "cofinite language"

showing 1 items of 1 documents

Complexity of operations on cofinite languages

2010

International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.

Nested wordTheoretical computer scienceSettore INF/01 - Informaticaautomata[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]regular operationReDoSComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technologyDescriptive complexity theorystate complexity01 natural sciencesComplement (complexity)Deterministic finite automaton010201 computation theory & mathematicsTheory of computation0202 electrical engineering electronic engineering information engineeringComputer Science::Programming LanguagesQuantum finite automata020201 artificial intelligence & image processingNondeterministic finite automatoncofinite languageMathematics
researchProduct